class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int mod = 1000000007;
        int n=s.size();
        if(n==0||n==1) return n;
        vector<vector<long long>> dp(n,vector<long long>(n,0));
        vector<vector<int>> nextpre(n,vector<int>(4,-1));
        vector<vector<int>> lastpre(n,vector<int>(4,-1));

        vector<int> last(4,-1);
        for(int i=0;i<n;i++){
            for(int c=0;c<4;c++){
                lastpre[i][c]=last[c];
            }
            int cur = s[i]-'a';
            last[cur] = i;
        }

        fill(last.begin(),last.end(),-1);
        for(int i=n-1;i>=0;i--){
            for(int c=0;c<4;c++){
                nextpre[i][c]=last[c];
            }
            int cur = s[i]-'a';
            last[cur]=i;
        }

        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(i==j){
                    dp[i][j]=1;
                }else{
                    if(s[i]!=s[j]){
                        dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;
                    }else{
                        int low = nextpre[i][s[i]-'a'];
                        int high = lastpre[j][s[j]-'a'];
                        if(low>high){
                            dp[i][j]=(2*dp[i+1][j-1]+2)%mod;
                        }else if(low==high){
                            dp[i][j]=(2*dp[i+1][j-1]+1)%mod;
                        }else{
                            dp[i][j]=(2*dp[i+1][j-1]-dp[low+1][high-1]+mod)%mod;
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
    }
};
